package DataStructureAndAlgorithm.BaseAlgorithm.Sort.QuickSort;
import java.util.*;
//快速选择算法，时间复杂度为O(2n)即O(n)
//因为，每次只要考虑一半的数
public class quicksort_786 {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++){
            nums[i] = in.nextInt();
        }
        int res =  quick_sort(nums,0,n - 1,k);
        System.out.print(res);
    }
    static int quick_sort(int[] nums,int left,int right,int k){
        if (left == right)return nums[left];
        int x = nums[left];
        int i = left - 1;
        int j = right + 1;
        while (i < j){
            do{i++;}while(nums[i] < x);
            do{j--;}while(nums[j] > x);
            if (i < j){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        //对于每次快排，都保证小于x的数在x的左边，大于x的数在x的右边，所以，利用这个性质，可以得到：
        //如果左边的数的个数大于k，则第k小的数，一定在左边的序列中，反之在右边的序列中
        int leftLen = j - left + 1;
        if (k <= leftLen){
            return quick_sort(nums,left,j,k);
        }
        return quick_sort(nums,j + 1,right,k - leftLen);
    }
}
/*

给定一个长度为 n
的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k

个数。
输入格式

第一行包含两个整数 n
和 k

。

第二行包含 n
个整数（所有整数均在 1∼109

范围内），表示整数数列。
输出格式

输出一个整数，表示数列的第 k

小数。
数据范围

1≤n≤100000
,
1≤k≤n

输入样例：

5 3
2 4 1 5 3

输出样例：

3

 */